package leetcode;

/**
 * 121. 买卖股票的最佳时机      https://leetcode.cn/problems/best-time-to-buy-and-sell-stock
 */
public class LeetCode121 {

    // 1、暴力递归
    public static int maxProfit1(int[] prices) {
        if (prices.length < 2) {
            return 0;
        }
        return dfs(0, prices.length, prices, false, 0, false);
    }

    private static int dfs(int index, int level, int[] prices, boolean buy, int ans, boolean flag) {
        if (index == level || flag) {
            return ans;
        }
        int no = dfs(index + 1, level, prices, buy, ans, false);
        int yes;
        if (buy) {
            yes = dfs(index + 1, level, prices, false, ans + prices[index], true);
        } else {
            yes = dfs(index + 1, level, prices, true, ans - prices[index], false);
        }
        return Math.max(no, yes);
    }

    // 2、一次遍历
    public static int maxProfit(int[] prices) {
        if (prices.length < 2) {
            return 0;
        }
        int minPrice = Integer.MAX_VALUE;
        int ans = 0;
        for (int i = 0; i < prices.length; i++) {
            minPrice = Math.min(minPrice, prices[i]);
            ans = Math.max(ans, prices[i] - minPrice);
        }
        return ans;
    }

    // 3、动态规划
    public static int maxProfit3(int[] prices) {
        if (prices.length < 2) {
            return 0;
        }
        int[][] dp = new int[prices.length][2];
        dp[0][0] = 0;
        dp[0][1] -= prices[0];

        for (int i = 1; i < prices.length; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
        }
        return dp[prices.length - 1][0];
    }

    public static void main(String[] args) {
        int[] prices = {7, 1, 5, 3, 6, 4};  // 5
        System.out.println(maxProfit(prices));
        int[] prices1 = {7, 6, 4, 3, 1};  // 0
        System.out.println(maxProfit(prices1));
    }
}
